Qué (quién) es B-coloring - definición
B-coloring
![Example of B-coloring of [[Shrikhande graph]] with 6 colors: highlighted nodes have neighbors in each other colors. Since each node is adjacent to another 6, a 7-color B-coloring may be possible.](https://commons.wikimedia.org/wiki/Special:FilePath/Graph b coloring example.svg?width=200 "Example of B-coloring of [[Shrikhande graph]] with 6 colors: highlighted nodes have neighbors in each other colors. Since each node is adjacent to another 6, a 7-color B-coloring may be possible.")
In graph theory, a b-coloring of a graph is a coloring of the vertices where each color class contains a vertex that has a neighbor in all other color classes.
graph colouring
ASSIGNMENT OF COLORS TO ELEMENTS OF A GRAPH SUBJECT TO CERTAIN CONSTRAINTS
Colouring algorithm; Coloring algorithm; Graph coloring algorithm; Chromatic number; Graph colouring problems; Graph coloring problem; Colored graph; Graph Colouring; Vertex chromatic number; K-vertex colorable; Vertex color; Graph colouring problem; Graph colouring; Three-Colorable Graph; Three-colorable graph; Vertex-colouring; Vertex colouring; Vertex coloring; Coloring problem; Colouring problem; Two-colorable graph; Graph two-coloring; Graph Two-Coloring; Graph coloration; Graph color; K-colouring; 3-colourability; Colourability; Proper coloring; K-coloring; Network coloring; Network colouring; K-chromatic graph; Distributed graph coloring; Cole–Vishkin algorithm; Cole-Vishkin algorithm; Mycielski's theorem; K-colorable; Unlabeled coloring; Vector chromatic number; Face coloring; Algorithms for graph coloring; Parallel algorithms for graph coloring; Applications of graph coloring; Decentralized graph coloring; Computational complexity of graph coloring
<application> A constraint-satisfaction problem often used
as a test case in research, which also turns out to be
equivalent to certain real-world problems (e.g. {register
allocation}). Given a connected graph and a fixed number of
colours, the problem is to assign a colour to each node,
subject to the constraint that any two connected nodes cannot
be assigned the same colour. This is an example of an
NP-complete problem.
See also four colour map theorem.
chromatic number
ASSIGNMENT OF COLORS TO ELEMENTS OF A GRAPH SUBJECT TO CERTAIN CONSTRAINTS
Colouring algorithm; Coloring algorithm; Graph coloring algorithm; Chromatic number; Graph colouring problems; Graph coloring problem; Colored graph; Graph Colouring; Vertex chromatic number; K-vertex colorable; Vertex color; Graph colouring problem; Graph colouring; Three-Colorable Graph; Three-colorable graph; Vertex-colouring; Vertex colouring; Vertex coloring; Coloring problem; Colouring problem; Two-colorable graph; Graph two-coloring; Graph Two-Coloring; Graph coloration; Graph color; K-colouring; 3-colourability; Colourability; Proper coloring; K-coloring; Network coloring; Network colouring; K-chromatic graph; Distributed graph coloring; Cole–Vishkin algorithm; Cole-Vishkin algorithm; Mycielski's theorem; K-colorable; Unlabeled coloring; Vector chromatic number; Face coloring; Algorithms for graph coloring; Parallel algorithms for graph coloring; Applications of graph coloring; Decentralized graph coloring; Computational complexity of graph coloring
<mathematics> The smallest number of colours necessary to
colour the nodes of a graph so that no two adjacent nodes
have the same colour.
See also: four colour map theorem.
{Graph Theory Lessons
(http://utc.edu/chromatic numbercpmawata/petersen/lesson8.htm) }.
{Eric Weisstein's World Of Mathematics
(http://mathworld.wolfram.com/ChromaticNumber.html) }.
{The Geometry Center
(http://geom.umn.edu/chromatic numberzarembe/grapht1.html) }.
(2000-03-18)
